package string;

/**
 * 讲一个字符串切成全部是回文字串，最少需要多少刀
 * 时间复杂度:O(n^2)
 *
 * @author Liaorun
 */
public class PalindromeMinCut {

    public static void main(String[] args) {
        System.out.println(minCut("123"));
        System.out.println(minCut("1232"));

        System.out.println(minParts("123"));
    }

    public static int minParts(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        if (s.length() == 1) {
            return 1;
        }

        // 切的刀数 =  块数 - 1
        return process(s.toCharArray(), 0) - 1;
    }

    /**
     * str[i..]最少能分割成多少回文的部分,递归版本解法
     * 返回最少的部分数
     *
     * @param str 字符串
     * @param i   开始位置
     * @return
     */
    private static int process(char[] str, int i) {
        // base case，没有字符的时候不是回文结构
        if (i == str.length) {
            return 0;
        }

        boolean[][] record = record(str);
        int ans = Integer.MAX_VALUE;
        // 尝试每一个end,如果str[i..end]这个部分是回文
        // 就去尝试这个部分作为第一块的情况
        for (int end = i; end < str.length; end++) {
            if (record[i][end]) {
                // str[i..]拆成：第一块为str[i..end],递归划分后面的部分
                // 有更少的划分次数 就更新
                ans = Math.min(ans, 1 + process(str, end + 1));
            }
        }

        return ans;
    }

    /**
     * 验证字符串的一部分字串是不是回文结构
     * 如果这里使用遍历判断的方法，那么整个算法的复杂度就是O（n^3)的
     *
     * @param str 字符串
     * @param l   子串开始位置
     * @param r   子串结束位置
     * @return true - 是回文结构,false - 不是回文结构
     */
    private static boolean valid(char[] str, int l, int r) {

        return false;
    }

    /**
     * str[i..]最少能分割成多少回文的部分,动态规划解法
     *
     * @param str 字符串
     * @return 最少切几刀，子串全是回文结构
     */
    public static int minCut(String str) {
        if (str == null || "".equals(str)) {
            return 0;
        }

        char[] chars = str.toCharArray();
        int length = chars.length;

        // 从左向右的动态规划表格
        int[] dp = new int[length + 1];
        dp[length] = 0;
        // 最后一个位置的字符可以最少分成的回文子串个数为1
        dp[length - 1] = 1;
        // 获取每一个子串是不是回文结构的二维表
        boolean[][] p = record(chars);

        for (int i = length - 2; i >= 0; i--) {
            // 假设有几个字符就切成几个回文（平凡解）
            dp[i] = chars.length - i;
            for (int j = i; j < length; j++) {
                if (p[i][j]) {
                    // 下标i到j是回文，则比平凡解更好，更新
                    // 更新为j+1..length-1这段字符串最少分成的回文子串个数 + 1
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }

            // 内部for结束，可以得到 i..length-1的子串最少可以分成多上个回文子串
        }

        // 切的刀数 =  块数 - 1
        return dp[0] - 1;
    }

    /**
     * 一个字符串的子串是不是回文结构
     *
     * @param str 字符串
     * @return
     */
    private static boolean[][] record(char[] str) {
        boolean[][] record = new boolean[str.length][str.length];
        record[str.length - 1][str.length - 1] = true;

        for (int i = 0; i < str.length - 1; i++) {
            // 二维正方形矩阵的对角线全为true -> 只有一个字符的情况必是回文
            record[i][i] = true;
            // 对角线右上方最靠近的斜线 -> 只有两个字符的情况，只要两个字符相等就是回文
            record[i][i + 1] = str[i] == str[i + 1];
        }
        for (int row = str.length - 3; row >= 0; row--) {
            for (int col = row + 2; col < str.length; col++) {
                // 首尾的字符相等 && 左下角格子的值也为true（除了首尾剩余的子串也是回文）
                record[row][col] = str[row] == str[col] && record[row + 1][col - 1];
            }
        }
        return record;
    }
}
